#ifndef _VL_LINKED_LIST__H_
#define _VL_LINKED_LIST__H_

/**
 * +======================================================================================================================+
 * @Author: CimZzz
 * @Date: 2023-07-18 14:56:11
 * 
 * 代码分割块，以下内容涉及: 
 * 
 * 链表数据结构
 */

#include <initializer_list>
#include <type_traits>

#include "vl_structure_exception.h"

namespace VL {

template<typename ValueType>
class SimpleLinkedList {
private:
	friend class ListPoint;
	struct _LinkedNode;
	using _LinkedNodePtr = _LinkedNode*;
	using _ValueTypePtr = ValueType*;

	struct _LinkedNode {
		_LinkedNode(const ValueType& value): value(value), front(nullptr), next(nullptr) {}
		_LinkedNode(ValueType&& value): value(value), front(nullptr), next(nullptr) {}
		ValueType value;
		_LinkedNodePtr front;
		_LinkedNodePtr next;
	};
public:
	// @Author: CimZzz
	// @Date: 2023-07-19 11:08:21
	// 列表点, 可以通过列表点插入到指定位置
	class ListPoint {
	public:
		ListPoint(): isHasPoint(false), _pointPtr(nullptr) {}

		bool isValid() const { return this->isHasPoint; }
	private:
		friend class SimpleLinkedList;
		ListPoint(_LinkedNodePtr pointPtr): isHasPoint(true), _pointPtr(pointPtr) {}
		bool isHasPoint;
		_LinkedNodePtr _pointPtr;
	};

public:

	// @Author: CimZzz
	// @Date: 2023-07-18 15:00:17
	// 缺省构造函数

	explicit SimpleLinkedList(): 
		frontPtr(nullptr),
		tailPtr(nullptr),
		_count(0) {}

	// @Author: CimZzz
	// @Date: 2023-07-18 15:23:46
	// 明确类型构造函数

	SimpleLinkedList(const SimpleLinkedList<ValueType>& otherList): 
		frontPtr(nullptr),
		tailPtr(nullptr),
		_count(0) {
		for(const ValueType& iter : otherList) {
			this->push_back(iter);
		}
	}
	SimpleLinkedList(SimpleLinkedList<ValueType>&& otherList): 
		frontPtr(otherList.frontPtr),
		tailPtr(otherList.tailPtr),
		_count(otherList._count) {
		otherList.frontPtr = nullptr;
		otherList.tailPtr = nullptr;
		otherList._count = 0;
	}
	SimpleLinkedList(const std::initializer_list<ValueType>& initList): 
		frontPtr(nullptr),
		tailPtr(nullptr),
		_count(0) {
		for(const ValueType& iter : initList) {
			this->push_back(iter);
		}
	}
	
	// @Author: CimZzz
	// @Date: 2023-07-18 15:00:46
	// 析构函数
	~SimpleLinkedList() {
		while(this->frontPtr != nullptr) {
			_LinkedNodePtr cur = this->frontPtr;
			this->frontPtr = this->frontPtr->next;
			delete cur;
		}
	}

public:
	// @Author: CimZzz
	// @Date: 2023-07-18 15:28:46
	// 追加方法

	ListPoint push_back(const ValueType& value) {
		_LinkedNodePtr newNode = new _LinkedNode(value);
		return this->_insertBack(newNode);
	}
	ListPoint push_back(ValueType&& value) {
		_LinkedNodePtr newNode = new _LinkedNode(value);
		return this->_insertBack(newNode);
	}

	ListPoint push_back(const ValueType& value, const ListPoint& point) {
		_LinkedNodePtr newNode = new _LinkedNode(value);
		return this->_insertBack(newNode, point);
	}
	ListPoint push_back(ValueType&& value, const ListPoint& point) {
		_LinkedNodePtr newNode = new _LinkedNode(value);
		return this->_insertBack(newNode, point);
	}

	// @Author: CimZzz
	// @Date: 2023-07-18 15:47:59
	// 隐式转换追加方法

	/**
	 * ValueType 为指针, ImplicitType 为解指针类型
	 * 需要满足以下几点:
	 * 1. ValueType 支持拷贝构造函数
	 * 
	 * @note 需要注意, 该方法会调用拷贝构造函数创建一个新的对象指针插入到链表
	 */
	template<typename ImplicitType, typename std::enable_if<
		std::is_pointer<ValueType>::value &&
		std::is_same<typename std::remove_pointer<ValueType>::type, ImplicitType>::value &&
		std::is_constructible<ImplicitType, const ImplicitType&>::value
	, bool>::type = true>
	ListPoint push_back(const ImplicitType& implicitValue) {
		_LinkedNodePtr newNode = new _LinkedNode(new ImplicitType(implicitValue));
		return this->_insertBack(newNode);
	}
	template<typename ImplicitType, typename std::enable_if<
		std::is_pointer<ValueType>::value &&
		std::is_same<typename std::remove_pointer<ValueType>::type, ImplicitType>::value &&
		std::is_constructible<ImplicitType, const ImplicitType&>::value
	, bool>::type = true>
	ListPoint push_back(const ImplicitType& implicitValue, const ListPoint& point) {
		_LinkedNodePtr newNode = new _LinkedNode(new ImplicitType(implicitValue));
		return this->_insertBack(newNode, point);
	}

	/**
	 * ValueType 为指针, ImplicitType 为解指针类型
	 * 需要满足以下几点:
	 * 1. ValueType 支持移动构造函数
	 * 
	 * @note 需要注意, 该方法会调用移动构造函数创建一个新的对象指针插入到链表
	 */
	template<typename ImplicitType, typename std::enable_if<
		std::is_pointer<ValueType>::value &&
		std::is_same<typename std::remove_pointer<ValueType>::type, ImplicitType>::value &&
		std::is_constructible<ImplicitType, ImplicitType&&>::value
	, bool>::type = true>
	ListPoint push_back(ImplicitType&& implicitValue) {
		_LinkedNodePtr newNode = new _LinkedNode(new ImplicitType(implicitValue));
		return this->_insertBack(newNode);
	}
	template<typename ImplicitType, typename std::enable_if<
		std::is_pointer<ValueType>::value &&
		std::is_same<typename std::remove_pointer<ValueType>::type, ImplicitType>::value &&
		std::is_constructible<ImplicitType, ImplicitType&&>::value
	, bool>::type = true>
	ListPoint push_back(ImplicitType&& implicitValue, const ListPoint& point) {
		_LinkedNodePtr newNode = new _LinkedNode(new ImplicitType(implicitValue));
		return this->_insertBack(newNode, point);
	}

	// @Author: CimZzz
	// @Date: 2023-07-18 16:18:12
	// 插入头部方法

	ListPoint push_front(const ValueType& value) {
		_LinkedNodePtr newNode = new _LinkedNode(value);
		return this->_insertFront(newNode);
	}
	ListPoint push_front(ValueType&& value) {
		_LinkedNodePtr newNode = new _LinkedNode(value);
		return this->_insertFront(newNode);
	}

	ListPoint push_front(const ValueType& value, const ListPoint& point) {
		_LinkedNodePtr newNode = new _LinkedNode(value);
		return this->_insertFront(newNode, point);
	}
	ListPoint push_front(ValueType&& value, const ListPoint& point) {
		_LinkedNodePtr newNode = new _LinkedNode(value);
		return this->_insertFront(newNode, point);
	}

	// @Author: CimZzz
	// @Date: 2023-07-18 15:47:59
	// 隐式转换插入头部方法

	/**
	 * ValueType 为指针, ImplicitType 为解指针类型
	 * 需要满足以下几点:
	 * 1. ValueType 支持拷贝构造函数
	 * 
	 * @note 需要注意, 该方法会调用拷贝构造函数创建一个新的对象指针插入到链表
	 */
	template<typename ImplicitType, typename std::enable_if<
		std::is_pointer<ValueType>::value &&
		std::is_same<typename std::remove_pointer<ValueType>::type, ImplicitType>::value &&
		std::is_constructible<ImplicitType, const ImplicitType&>::value
	, bool>::type = true>
	ListPoint push_front(const ImplicitType& implicitValue) {
		_LinkedNodePtr newNode = new _LinkedNode(new ImplicitType(implicitValue));
		return this->_insertFront(newNode);
	}

	template<typename ImplicitType, typename std::enable_if<
		std::is_pointer<ValueType>::value &&
		std::is_same<typename std::remove_pointer<ValueType>::type, ImplicitType>::value &&
		std::is_constructible<ImplicitType, const ImplicitType&>::value
	, bool>::type = true>
	ListPoint push_front(const ImplicitType& implicitValue, const ListPoint& point) {
		_LinkedNodePtr newNode = new _LinkedNode(new ImplicitType(implicitValue));
		return this->_insertFront(newNode, point);
	}

	/**
	 * ValueType 为指针, ImplicitType 为解指针类型
	 * 需要满足以下几点:
	 * 1. ValueType 支持移动构造函数
	 * 
	 * @note 需要注意, 该方法会调用移动构造函数创建一个新的对象指针插入到链表
	 */
	template<typename ImplicitType, typename std::enable_if<
		std::is_pointer<ValueType>::value &&
		std::is_same<typename std::remove_pointer<ValueType>::type, ImplicitType>::value &&
		std::is_constructible<ImplicitType, ImplicitType&&>::value
	, bool>::type = true>
	ListPoint push_front(ImplicitType&& implicitValue) {
		_LinkedNodePtr newNode = new _LinkedNode(new ImplicitType(implicitValue));
		return this->_insertFront(newNode);
	}
	template<typename ImplicitType, typename std::enable_if<
		std::is_pointer<ValueType>::value &&
		std::is_same<typename std::remove_pointer<ValueType>::type, ImplicitType>::value &&
		std::is_constructible<ImplicitType, ImplicitType&&>::value
	, bool>::type = true>
	ListPoint push_front(ImplicitType&& implicitValue, const ListPoint& point) {
		_LinkedNodePtr newNode = new _LinkedNode(new ImplicitType(implicitValue));
		return this->_insertFront(newNode, point);
	}

public:
	// @Author: CimZzz
	// @Date: 2023-07-24 17:08:27
	// 值引用
	struct value_iterator {
		value_iterator(const value_iterator&) = delete;
		value_iterator(value_iterator&& ref): ptr(ref.ptr) {
			ref.ptr = nullptr;
		}
		value_iterator(_LinkedNodePtr ptr): ptr(ptr) {}
		~value_iterator() {
			if(this->ptr != nullptr) {
				delete this->ptr;
				this->ptr = nullptr;
			}
		}

		ValueType* get() const {
			if(this->ptr == nullptr) {
				return nullptr;
			}
			return &this->ptr->value;
		}

		ValueType& operator*() {
			return this->ptr->value;
		}

		ValueType* operator->() {
			return &this->ptr->value;
		}
	private:
		_LinkedNodePtr ptr;
	};

	// @Author: CimZzz
	// @Date: 2023-07-24 17:05:05
	// 移除方法

	/**
	 * @Author: CimZzz
	 * @Date: 2023-07-24 17:06:47
	 * 
	 * 移除尾部
	 */
	value_iterator pop_back() {
		if(this->frontPtr == nullptr) {
			return value_iterator(nullptr);
		}
		_LinkedNodePtr deleteNode = this->tailPtr;
		this->tailPtr = this->tailPtr->front;
		if(this->tailPtr == nullptr) {
			this->frontPtr = nullptr;
			this->tailPtr = nullptr;
		} else {
			this->tailPtr->next = nullptr;
		}
		deleteNode->front = nullptr;
		this->_count --;
		return value_iterator(deleteNode);
	}

	/**
	 * @Author: CimZzz
	 * @Date: 2023-07-24 17:06:56
	 * 
	 * 移除头部
	 */
	value_iterator pop_front() {
		if(this->frontPtr == nullptr) {
			return value_iterator(nullptr);
		}
		_LinkedNodePtr deleteNode = this->frontPtr;
		this->frontPtr = this->frontPtr->next;
		if(this->frontPtr == nullptr) {
			this->frontPtr = nullptr;
			this->tailPtr = nullptr;
		} else {
			this->frontPtr->front = nullptr;
		}
		deleteNode->next = nullptr;
		this->_count --;
		return value_iterator(deleteNode);
	}

	/**
	 * @Author: CimZzz
	 * @Date: 2023-07-26 10:48:30
	 * 
	 * 根据列表点移除元素
	 * 
	 * @param 列表点
	 */
	value_iterator pop_position(ListPoint& point) {
		if(!point.isHasPoint) {
			return value_iterator(nullptr);
		}
		point.isHasPoint = false;
		_LinkedNodePtr deleteNode = point._pointPtr;
		if(deleteNode == this->frontPtr) {
			return pop_front();
		} else if(deleteNode == this->tailPtr) {
			return pop_back();
		} else {
			deleteNode->front->next = deleteNode->next;
			deleteNode->next->front = deleteNode->front;
			deleteNode->front = nullptr;
			deleteNode->next = nullptr;
			this->_count --;
			return value_iterator(deleteNode);
		}
	}

private:
	inline ListPoint _insertBack(_LinkedNodePtr ptr) {
		if(this->frontPtr == nullptr) {
			this->frontPtr = ptr;
			this->tailPtr = ptr;
		} else {
			ptr->front = this->tailPtr;
			this->tailPtr->next = ptr;
			this->tailPtr = ptr;
		}
		this->_count ++;
		return ListPoint(ptr);
	}
	inline ListPoint _insertFront(_LinkedNodePtr ptr) {
		if(this->frontPtr == nullptr) {
			this->frontPtr = ptr;
			this->tailPtr = ptr;
		} else {
			this->frontPtr->front = ptr;
			ptr->next = this->frontPtr;
			this->frontPtr = ptr;
		}
		this->_count ++;
		return ListPoint(ptr);
	}
	inline ListPoint _insertBack(_LinkedNodePtr ptr, const ListPoint& point) {
		if(point.isHasPoint && this->frontPtr != nullptr) {
			ptr->next = point._pointPtr->next;
			ptr->front = point._pointPtr;
			if(point._pointPtr->next != nullptr) {
				point._pointPtr->next->front = ptr;
			}
			point._pointPtr->next = ptr;
			if(point._pointPtr == this->tailPtr) {
				this->tailPtr = ptr;
			}
		} else {
			if(this->frontPtr == nullptr) {
				this->frontPtr = ptr;
				this->tailPtr = ptr;
			} else {
				ptr->front = this->tailPtr;
				this->tailPtr->next = ptr;
				this->tailPtr = ptr;
			}
		}
		this->_count ++;
		return ListPoint(ptr);
	}
	inline ListPoint _insertFront(_LinkedNodePtr ptr, const ListPoint& point) {
		if(point.isHasPoint && this->frontPtr != nullptr) {
			ptr->next = point._pointPtr;
			ptr->front = point._pointPtr->front;
			if(point._pointPtr->front != nullptr) {
				point._pointPtr->front->next = ptr;
			}
			point._pointPtr->front = ptr;
			if(point._pointPtr == this->frontPtr) {
				this->frontPtr = ptr;
			}
		} else {
			if(this->frontPtr == nullptr) {
				this->frontPtr = ptr;
				this->tailPtr = ptr;
			} else {
				this->frontPtr->front = ptr;
				ptr->next = this->frontPtr;
				this->frontPtr = ptr;
			}
		}
		this->_count ++;
		return ListPoint(ptr);
	}

public:
	// @Author: CimZzz
	// @Date: 2023-07-18 15:28:21
	// 迭代方法

	// 定义迭代器
	struct iterator {
		iterator(_LinkedNodePtr ptr): ptr(ptr) {}
		bool operator==(const iterator& other) const {
			return ptr == other.ptr;
		}
		bool operator!=(const iterator& other) const {
			return ptr != other.ptr;
		}
		iterator& operator++() {
			if(ptr == nullptr) {
				return *this;
			}
			this->ptr = this->ptr->next;
			return *this;
		}
		iterator& operator++(int) {
			if(ptr == nullptr) {
				return *this;
			}
			this->ptr = this->ptr->next;
			return *this;
		}
		ValueType& operator*() {
			return ptr->value;
		}
		ValueType* operator->() {
			return ptr != nullptr ? &ptr->value : nullptr;
		}
	private:
		_LinkedNodePtr ptr;
	};
	struct const_iterator {
		const_iterator(_LinkedNodePtr ptr): ptr(ptr) {}

		bool operator==(const const_iterator& other) const {
			return ptr == other.ptr;
		}
		bool operator!=(const const_iterator& other) const {
			return ptr != other.ptr;
		}
		const_iterator& operator++() {
			if(ptr == nullptr) {
				return *this;
			}
			this->ptr = this->ptr->next;
			return *this;
		}
		const_iterator& operator++(int) {
			if(ptr == nullptr) {
				return *this;
			}
			this->ptr = this->ptr->next;
			return *this;
		}
		const ValueType& operator*() {
			return ptr->value;
		}
		const ValueType* operator->() {
			return ptr != nullptr ? &ptr->value : nullptr;
		}
	private:
		_LinkedNodePtr ptr;
	};

	inline iterator begin() {
		return iterator(this->frontPtr);
	}
	inline iterator end() {
		return iterator(nullptr);
	}
	inline const_iterator begin() const {
		return const_iterator(this->frontPtr);
	}
	inline const_iterator end() const {
		return const_iterator(nullptr);
	}
	inline iterator fromPoint(const ListPoint& point) {
		if(point.isHasPoint) {
			return iterator(point._pointPtr);
		}
		return iterator(nullptr);
	}
	
public:
	// @Author: CimZzz
	// @Date: 2023-07-18 15:33:41
	// 获取尺寸方法

	inline size_t count() const {
		return this->_count;
	}
	inline bool empty() const {
		return this->_count == 0;
	}
	inline bool not_empty() const {
		return this->_count > 0;
	}
	inline size_t size() const {
		return this->_count;
	}
	inline size_t length() const {
		return this->_count;
	}

private:
	// 链表首节点
	_LinkedNodePtr frontPtr;
	// 链表尾节点
	_LinkedNodePtr tailPtr;
	// 链表长度
	size_t _count;
};

}

#endif // end _VL_LINKED_LIST__H_